package test;

import bean.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/*
      题目
      98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
       数据
输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。
输入:
    2
   / \
  1   3
输出: true
 */
public class letcode98_yanzhenerchashu {
    private   static Integer last;  //默认值为空
    //判断是否为二叉树   采用中序遍历 ，结果必然是升序
    //复制度为o(n)
    public   static  boolean isTrueTree(TreeNode root){
        if(root==null)
            return true;
        if(!isTrueTree(root.left)) return false;
        if(last!=null&&root.val<=last) return false;    //保证遍历第二次才开始比较
        last=root.val;
        if(!isTrueTree(root.right)) return false;
        return true;
    }
    //方法二  遍历二叉树时就确定每个节点的上下界   不管啥方式遍历都可以  本次是前序遍历
    public  static boolean isTrueTree1(TreeNode root,Integer min,Integer max){
        if(root==null) return true;
        if(min!=null&&root.val<=min) return false;
        if(max!=null&&root.val>=max) return false;
        if(!isTrueTree1(root.left,min,root.val )) return false;   //如果递归出来结果为false 那么就结束递归   遍历下一个左节点范围（该节点本身的最小值，该节点的值）
        if(!isTrueTree1(root.right,root.val,max)) return false;//遍历下一个右节点（该节点的值，该节点本身的最大值）
        return  true;
    }
    //方法三广度优先遍历
    public  static boolean isTrueTree2(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode > queue=new LinkedList<>();
        Queue<Integer > min=new LinkedList<>();
        Queue<Integer > max=new LinkedList<>();
        queue.offer(root);
        min.offer(null);
        max.offer(null);
        while (!queue.isEmpty()){
            TreeNode t=queue.poll();
            Integer mins=min.poll();
            Integer maxs=max.poll();
            if(mins!=null&&t.val<=mins) return false;
            if(maxs!=null&&t.val>=maxs) return false;
            if(t.left!=null){
                queue.offer(t.left);   //先加左边
                min.offer(mins);
                max.offer(t.val);
            }
            if(t.right!=null){
                queue.offer(t.right);  //再加右边
                min.offer(t.val);
                max.offer(maxs);
            }
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode t=new TreeNode(1);
        TreeNode t1=new TreeNode(2);
        TreeNode t2=new TreeNode(3);
//        TreeNode t3=new TreeNode(4);
//        TreeNode t4=new TreeNode(5);
//        TreeNode t5=new TreeNode(6);
//        TreeNode t6=new TreeNode(7);
//        t.left=t1;
//        t.right=t2;
//        t1.left=t3;
//        t1.right=t4;
//        t2.right=t5;
//        t4.left=t6;
        t1.left=t;
        t1.right=t2;
        //System.out.println(isTrueTree1(t1,null,null));
        System.out.println(isTrueTree2(t1));
    }

}
